#include <iostream>

#include "iostream"
#include "vector"
#include "unordered_map"
#include "unordered_set"
#include "algorithm"
#include "string"
#include "list"
#include "string.h"



class OneLoop {
public:
    int m_cnt;
    int rela[100][100];
    std::vector<int> room_stus[100];
    int res=INT_MAX;
    OneLoop(){
        memset(rela,0,sizeof rela);
    }
    //深度即房间数
    bool dfs(int room_cnt,int stu_i){
        if(room_cnt>=res){
            return false;
        }
        if(stu_i==m_cnt){
            if(room_cnt<res){
                res=room_cnt;
            }
            return true;
        }
        for(int i=0;i<room_cnt;i++){
            bool stu_can_enter= true;
            for(auto s:room_stus[i]){
                if(rela[s][stu_i]){
                    stu_can_enter=false;
                    break;}}
            if(stu_can_enter){
                room_stus[i].push_back(stu_i);
                if(dfs(room_cnt,stu_i+1)){}
                room_stus[i].pop_back();
            }
        }
        room_stus[room_cnt].push_back(stu_i);
        if(dfs(room_cnt+1,stu_i+1)){}
        room_stus[room_cnt].pop_back();
        return false;
    }
    bool run(int a,int b
    ) {
        m_cnt=a;
        for(int i=0;i<b;i++){

            int s1,s2;std::cin>>s1>>s2;
            rela[s1-1][s2-1]=1;
            rela[s2-1][s1-1]=1;
        }
        dfs(1,0);
        printf("%d\n",res);
        return true;
    }
};

class Solution {
public:
    void run() {

        bool first = true;
        int a, b, c, d, e;
        //        std::cin >> a;

        while (std::cin>>a>>b) {

            OneLoop l;
            if (!l.run(a,b)) {
                //                return;
            }
        }


    }
};

int main() {
    //    bool cur_num= true;
    Solution().run();
    return 0;
}

